1848E - Vika and Stone Skipping - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll _=1e6+5;
ll n,q,x,s=1,t,a[_],i,j,M;
ll qp(ll x,ll y){ll z=1;for(;y;y>>=1,x=x*x%M)if(y&1)z=z*x%M;return z;}
void cal(ll x,bool f){
	ll y=0;
	while(x%M==0)x/=M,y++;
	if(f)t+=y,s=s*x%M;
	else t-=y,s=s*qp(x,M-2)%M;
}
void p(ll x){
	while(1^x&1)x>>=1;
	for(i=3;i*i<=x;i+=2)if(x%i==0){
		cal(a[i]+1,0);
		while(x%i==0)x/=i,a[i]++;
		cal(a[i]+1,1);
	}
	if(x>1)cal(a[x]+1,0),a[x]++,cal(a[x]+1,1);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>x>>q>>M;
	while(1^x&1)x>>=1;
	for(i=3;i*i<=x;i+=2)if(x%i==0){
		cal(a[i]+1,0);
		while(x%i==0)x/=i,a[i]++;
		cal(a[i]+1,1);
	}
	if(x>1){if(x<_)a[x]++;s=s*2%M;}
	while(q--)cin>>x,p(x),cout<<(t?0ll:s)<<'\n';
}